<!DOCTYPE html>
<html>

<head>
    <meta charset='utf-8'>
    <meta http-equiv='X-UA-Compatible' content='IE=edge'>
    <title>寻找两个有序数组的中位数</title>
    <meta name='viewport' content='width=device-width, initial-scale=1'>
    <style>
        .box {
            display: flex;
            padding: 5%;
        }

        .left-wrap {
            width: 40%;
        }

        pre {
            text-align: left;
            margin-left: -20%;
        }
    </style>
</head>

<body>
    <div class="box">
        <div class="left-wrap">
            <div class="notranslate">
                <p>给定一个字符串 <code>s</code>，找到 <code>s</code> 中最长的回文子串。你可以假设&nbsp;<code>s</code> 的最大长度为 1000。</p>

                <p><strong>示例 1：</strong></p>

                <pre>
                    <strong>输入:</strong> "babad"
                    <strong>输出:</strong> "bab"
                    <strong>注意:</strong> "aba" 也是一个有效答案。
                    </pre>

                <p><strong>示例 2：</strong></p>

                <pre>
                    <strong>输入:</strong> "cbbd"
                    <strong>输出:</strong> "bb"
                </pre>
            </div>
        </div>
    </div>
</body>
<script>
    /**
       给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
        回文的意思是正着念和倒着念一样，如：上海自来水来自海上
        示例 1：

        输入: "babad"
        输出: "bab"
        注意: "aba" 也是一个有效答案。
        示例 2：

        输入: "cbbd"
        输出: "bb"

    */

    /**
    * @param {string} s
    * @return {string}
    思路
        标签：动态规划。
        动态规划：通过子问题答案来解决大问题答案；子问题都需要是离散且不依赖其他子问题（详可见《算法图解》第九章「动态规划」）。
        回文字符串：正读和反读都一样，""、"a"、"aa"、"aba"、"abcba" 等。
        可将字符串 S 反转为 S'，通过 S 和 S' 比较，利用动态规划先得到 最长公共子串。
        S 和 S' 分别置于横、纵坐标，通过网格（二维数组）一一比较子串（每一个子串就是一个子问题），当前公共子串的长度等于前面公共子串的长度加一，网格记录当前公共子串的长度。
        通过最长公共子串的长度和结束位置，得到最长公共子串。
        S = aacdecaa 和 S' = aacedcaa 最长公共子串为 acc，不是回文子串，需要进一步判断最长公共子串是否为回文子串。
        caa 为 aac 的反向副本，通过检查反向子串 aac 的原始索引是否与子串 aac 索引相同，来排除反向副本的情况。
        不需要检查反向子串 aac 的每个字符，只需要检查反向子串末尾字符 c 的原始索引，是否等于子串 aac 的首字符 a 索引即可。
        时间复杂度：O(n^2) -- 两层遍历。
        空间复杂度：O(n^2) -- 二维数组。

    */

    var longestPalindrome = function (s) {
        if (s === "") {
            return "";
        }
        let cell = [], maxLen = 0, maxEnd = 0;
        for (let i = 0; i < s.length; i++) {
            cell.push([]);
            for (let j = 0; j < s.length; j++) {
                let beforeIndex = s.length - 1 - i;
                if (s[beforeIndex] === s[j]) {
                    if (i === 0 || j === 0) {
                        cell[i][j] = 1;
                    } else {
                        cell[i][j] = cell[i - 1][j - 1] + 1;
                    }
                } else {
                    cell[i][j] = 0;
                }
                if (cell[i][j] > maxLen) {
                    let firstIndex = j - cell[i][j] + 1;
                    if (beforeIndex === firstIndex) {
                        maxLen = cell[i][j];
                        maxEnd = j;
                    }
                }
            }
        }
        console.log(maxEnd + 1 - maxLen, maxEnd + 1)
        return s.slice(maxEnd + 1 - maxLen, maxEnd + 1)
    };


    console.log(longestPalindrome('babad'))

</script>

</html>